/* domain
        Dom_EmptyNode = EmptyNode              &
        Dom_Black = Black                      &
        Dom_Red = Red                          &         
        Dom_BlackNode \Un Dom_RedNode = Node   &
        Dom_BlackNode \Int Dom_RedNode = empty 
*/

sealed abstract class Tree
class Node(val left: Tree, val color: Color, val right: Tree) extends Tree
class EmptyNode extends Tree

sealed abstract class Color
class Red extends Color
class Black extends Color

object BlackNode {
  def apply(left: Tree, right: Tree): BlackNode = 
    new Node(left,Black(),right)
    
  def unapply(b: Node): Option[(Tree,Color,Tree)] =
    (b.color: Color) match {
      case Red() => None
      case Black() => Some(Tuple3(b.left,b.color,b.right))
  }
}

object RedNode {
  def apply(left: Tree, right: Tree): BlackNode = 
    new Node(left,Red(),right)
    
  def unapply(r: Node): Option[(Tree,Color,Tree)] =
    (r.color: Color) match {
      case Red() => Some(Tuple3(r.left,r.color,r.right))
      case Black() => None
    }
}

object EmptyNode {
  def apply(): EmptyNode = new EmptyNode()
  def unapply(e: EmptyNode): Boolean = true
}

object Red {
  def apply(): Red = new Red()
  def unapply(r: Red): Boolean = true
}

object Black {
  def apply(): Black = new Black()
  def unapply(b: Black): Boolean = true
}


object Test {
  def test(tree: Tree): Boolean = (tree: Tree) match {
    case BlackNode(_,_,RedNode(n: Node,_,_)) => true
    case BlackNode(_,_,RedNode(n: EmptyNode,_,_)) => true
    case BlackNode(_,_,BlackNode(_,_,_)) => true
    case BlackNode(_,_,EmptyNode()) => true
    case RedNode(_,_,_) => true
    case EmptyNode() => true
  }
} 
  

object Main {

  def main(args: Array[String]): Unit =  
    Test.test(BlackNode(EmptyNode(),RedNode(EmptyNode(),EmptyNode())))
}

